<HTML>
<!--
  -- Copyright (c) 1996-1999
  -- Silicon Graphics Computer Systems, Inc.
  --
  -- Permission to use, copy, modify, distribute and sell this software
  -- and its documentation for any purpose is hereby granted without fee,
  -- provided that the above copyright notice appears in all copies and
  -- that both that copyright notice and this permission notice appear
  -- in supporting documentation.  Silicon Graphics makes no
  -- representations about the suitability of this software for any
  -- purpose.  It is provided "as is" without express or implied warranty.
  --
  -- Copyright (c) 1994
  -- Hewlett-Packard Company
  --
  -- Permission to use, copy, modify, distribute and sell this software
  -- and its documentation for any purpose is hereby granted without fee,
  -- provided that the above copyright notice appears in all copies and
  -- that both that copyright notice and this permission notice appear
  -- in supporting documentation.  Hewlett-Packard Company makes no
  -- representations about the suitability of this software for any
  -- purpose.  It is provided "as is" without express or implied warranty.
  --
  -->
<Head>
<Title>list&lt;T, Alloc&gt;</Title>
<!-- Generated by htmldoc -->
</HEAD>
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 
	ALINK="#ff0000"> 
<IMG SRC="CorpID.gif" 
     ALT="SGI" HEIGHT="43" WIDTH="151"> 
<!--end header-->
<BR Clear>
<H1>list&lt;T, Alloc&gt;</H1>

<Table CellPadding=0 CellSpacing=0 width=100%>
<TR>
<TD Align=left><Img src = "containers.gif" Alt=""   WIDTH = "194"  HEIGHT = "38" ></TD>
<TD Align=right><Img src = "type.gif" Alt=""   WIDTH = "194"  HEIGHT = "39" ></TD>
</TR>
<TR>
<TD Align=left VAlign=top><b>Category</b>: containers</TD>
<TD Align=right VAlign=top><b>Component type</b>: type</TD>
</TR>
</Table>

<h3>Description</h3>
A <tt>list</tt> is a doubly linked list.  That is, it is a
<A href="Sequence.html">Sequence</A> that supports both forward and
backward traversal, and (amortized) constant time insertion and
removal of elements at the beginning or the end, or in the middle.
<tt>List</tt>s have the important property that insertion and splicing
do not invalidate iterators to list elements, and that even removal
invalidates only the iterators that point to the elements that are
removed.  The ordering of iterators may be changed (that is,
<tt>list&lt;T&gt;::iterator</tt> might have a different predecessor or
successor after a list operation than it did before), but the
iterators themselves will not be invalidated or made to point to
different elements unless that invalidation or mutation is
explicit. <A href="#1">[1]</A>
<P>
Note that singly linked lists, which only support forward traversal,
are also sometimes useful.  If you do not need backward traversal,
then <tt><A href="Slist.html">slist</A></tt> may be more efficient
than <tt>list</tt>.
<h3>Definition</h3>
Defined in the standard header <A href="list">list</A>, and in the nonstandard
backward-compatibility header <A href="list.h">list.h</A>.
<h3>Example</h3>
<pre>
list&lt;int&gt; L;
L.push_back(0);
L.push_front(1);
L.insert(++L.begin(), 2);
<A href="copy.html">copy</A>(L.begin(), L.end(), <A href="ostream_iterator.html">ostream_iterator</A>&lt;int&gt;(cout, &quot; &quot;));
// The values that are printed are 1 2 0
</pre>
<h3>Template parameters</h3>
<Table border>
<TR>
<TH>
Parameter
</TH>
<TH>
Description
</TH>
<TH>
Default
</TH>
</TR>
<TR>
<TD VAlign=top>
<tt>T</tt>
</TD>
<TD VAlign=top>
The <tt>list</tt>'s value type: the type of object that is stored in the list.
</TD>
<TD VAlign=top>
&nbsp;
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>Alloc</tt>
</TD>
<TD VAlign=top>
The <tt>list</tt>'s allocator, used for all internal memory management.
</TD>
<TD VAlign=top>
<tt><A href="Allocators.html">alloc</A></tt>
</TD>
</tr>
</table>
<h3>Model of</h3>
<A href="ReversibleContainer.html">Reversible Container</A>, <A href="FrontInsertionSequence.html">Front Insertion Sequence</A>, 
<A href="BackInsertionSequence.html">Back Insertion Sequence</A>.
<h3>Type requirements</h3>
None, except for those imposed by the requirements of 
<A href="ReversibleContainer.html">Reversible Container</A>, <A href="FrontInsertionSequence.html">Front Insertion Sequence</A>, and
<A href="BackInsertionSequence.html">Back Insertion Sequence</A>.
<h3>Public base classes</h3>
None.
<h3>Members</h3>
<Table border>
<TR>
<TH>
Member
</TH>
<TH>
Where defined
</TH>
<TH>
Description
</TH>
</TR>
<TR>
<TD VAlign=top>
<tt>value_type</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
The type of object, <tt>T</tt>, stored in the list.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>pointer</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
Pointer to <tt>T</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>reference</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
Reference to <tt>T</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>const_reference</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
Const reference to <tt>T</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>size_type</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
An unsigned integral type.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>difference_type</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
A signed integral type.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>iterator</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
Iterator used to iterate through a <tt>list</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>const_iterator</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
Const iterator used to iterate through a <tt>list</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>reverse_iterator</tt>
</TD>
<TD VAlign=top>
 <A href="ReversibleContainer.html">Reversible Container</A>
</TD>
<TD VAlign=top>
Iterator used to iterate backwards through a <tt>list</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>const_reverse_iterator</tt>
</TD>
<TD VAlign=top>
 <A href="ReversibleContainer.html">Reversible Container</A>
</TD>
<TD VAlign=top>
Const iterator used to iterate backwards through a <tt>list</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>iterator begin()</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
Returns an <tt>iterator</tt> pointing to the beginning of the <tt>list</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>iterator end()</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
Returns an <tt>iterator</tt> pointing to the end of the <tt>list</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>const_iterator begin() const</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
Returns a <tt>const_iterator</tt> pointing to the beginning of the <tt>list</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>const_iterator end() const</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
Returns a <tt>const_iterator</tt> pointing to the end of the <tt>list</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>reverse_iterator rbegin()</tt>
</TD>
<TD VAlign=top>
 <A href="ReversibleContainer.html">Reversible Container</A>
</TD>
<TD VAlign=top>
Returns a <tt>reverse_iterator</tt> pointing to the beginning of the
   reversed list.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>reverse_iterator rend()</tt>
</TD>
<TD VAlign=top>
 <A href="ReversibleContainer.html">Reversible Container</A>
</TD>
<TD VAlign=top>
Returns a <tt>reverse_iterator</tt> pointing to the end of the
   reversed list.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>const_reverse_iterator rbegin() const</tt>
</TD>
<TD VAlign=top>
 <A href="ReversibleContainer.html">Reversible Container</A>
</TD>
<TD VAlign=top>
Returns a <tt>const_reverse_iterator</tt> pointing to the beginning of the
   reversed list.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>const_reverse_iterator rend() const</tt>
</TD>
<TD VAlign=top>
 <A href="ReversibleContainer.html">Reversible Container</A>
</TD>
<TD VAlign=top>
Returns a <tt>const_reverse_iterator</tt> pointing to the end of the
   reversed list.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>size_type size() const</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
Returns the size of the <tt>list</tt>.  Note: you should not assume that
   this function is constant time.  It is permitted to be <i>O(N</i>), 
   where <i>N</i> is the number of elements in the <tt>list</tt>.  If you wish to
   test whether a <tt>list</tt> is empty, you should write <tt>L.empty()</tt> rather
   than <tt>L.size() == 0</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>size_type max_size() const</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
Returns the largest possible size of the <tt>list</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>bool empty() const</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
<tt>true</tt> if the <tt>list</tt>'s size is <tt>0</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>list()</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
Creates an empty list.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>list(size_type n)</tt>
</TD>
<TD VAlign=top>
 <A href="Sequence.html">Sequence</A>
</TD>
<TD VAlign=top>
Creates a list with <tt>n</tt> elements, each of which is a copy of <tt>T()</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>list(size_type n, const T&amp; t)</tt>
</TD>
<TD VAlign=top>
 <A href="Sequence.html">Sequence</A>
</TD>
<TD VAlign=top>
Creates a list with <tt>n</tt> copies of <tt>t</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>list(const list&amp;)</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
The copy constructor.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>
template &lt;class <A href="InputIterator.html">InputIterator</A>&gt;
list(InputIterator f, InputIterator l)
<A href="#2">[2]</A>
</pre>
</TD>
<TD VAlign=top>
 <A href="Sequence.html">Sequence</A>
</TD>
<TD VAlign=top>
Creates a list with a copy of a range.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>~list()</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
The destructor.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>list&amp; operator=(const list&amp;)</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
The assignment operator
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>reference front()</tt>
</TD>
<TD VAlign=top>
 <A href="FrontInsertionSequence.html">Front Insertion Sequence</A>
</TD>
<TD VAlign=top>
Returns the first element.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>const_reference front() const</tt>
</TD>
<TD VAlign=top>
 <A href="FrontInsertionSequence.html">Front Insertion Sequence</A>
</TD>
<TD VAlign=top>
Returns the first element.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>reference back()</tt>
</TD>
<TD VAlign=top>
 <A href="Sequence.html">Sequence</A>
</TD>
<TD VAlign=top>
Returns the last element.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>const_reference back() const</tt>
</TD>
<TD VAlign=top>
 <A href="BackInsertionSequence.html">Back Insertion Sequence</A>
</TD>
<TD VAlign=top>
Returns the last element.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void push_front(const T&amp;)</tt>
</TD>
<TD VAlign=top>
 <A href="FrontInsertionSequence.html">Front Insertion Sequence</A>
</TD>
<TD VAlign=top>
Inserts a new element at the beginning.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void push_back(const T&amp;)</tt>
</TD>
<TD VAlign=top>
 <A href="BackInsertionSequence.html">Back Insertion Sequence</A>
</TD>
<TD VAlign=top>
Inserts a new element at the end.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void pop_front()</tt>
</TD>
<TD VAlign=top>
 <A href="FrontInsertionSequence.html">Front Insertion Sequence</A>
</TD>
<TD VAlign=top>
Removes the first element.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void pop_back()</tt>
</TD>
<TD VAlign=top>
 <A href="BackInsertionSequence.html">Back Insertion Sequence</A>
</TD>
<TD VAlign=top>
Removes the last element.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void swap(list&amp;)</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
Swaps the contents of two lists.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>iterator insert(iterator pos, const T&amp; x)</tt>
</TD>
<TD VAlign=top>
 <A href="Sequence.html">Sequence</A>
</TD>
<TD VAlign=top>
Inserts <tt>x</tt> before <tt>pos</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>
template &lt;class <A href="InputIterator.html">InputIterator</A>&gt;
void insert(iterator pos, 
            InputIterator f, 
            InputIterator l)
<A href="#2">[2]</A>
</pre>
</TD>
<TD VAlign=top>
 <A href="Sequence.html">Sequence</A>
</TD>
<TD VAlign=top>
Inserts the range <tt>[f, l)</tt> before <tt>pos</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>
void insert(iterator pos, 
            size_type n, const T&amp; x)
</pre>
</TD>
<TD VAlign=top>
 <A href="Sequence.html">Sequence</A>
</TD>
<TD VAlign=top>
Inserts <tt>n</tt> copies of <tt>x</tt> before <tt>pos</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>iterator erase(iterator pos)</tt>
</TD>
<TD VAlign=top>
 <A href="Sequence.html">Sequence</A>
</TD>
<TD VAlign=top>
Erases the element at position <tt>pos</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>iterator erase(iterator first, iterator last)</tt>
</TD>
<TD VAlign=top>
 <A href="Sequence.html">Sequence</A>
</TD>
<TD VAlign=top>
Erases the range <tt>[first, last)</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void clear()</tt>
</TD>
<TD VAlign=top>
 <A href="Sequence.html">Sequence</A>
</TD>
<TD VAlign=top>
Erases all of the elements.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void resize(n, t = T())</tt>
</TD>
<TD VAlign=top>
 <A href="Sequence.html">Sequence</A>
</TD>
<TD VAlign=top>
Inserts or erases elements at the end such that the size becomes <tt>n</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void splice(iterator pos, list&amp; L)</tt>
</TD>
<TD VAlign=top>
<tt>list</tt>
</TD>
<TD VAlign=top>
See below.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>
void splice(iterator pos, 
            list&amp; L,
            iterator i)
</pre>
</TD>
<TD VAlign=top>
<tt>list</tt>
</TD>
<TD VAlign=top>
See below.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>
void splice(iterator pos,
            list&amp; L, 
            iterator f, iterator l)
</pre>
</TD>
<TD VAlign=top>
<tt>list</tt>
</TD>
<TD VAlign=top>
See below.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void remove(const T&amp; value)</tt>
</TD>
<TD VAlign=top>
<tt>list</tt>
</TD>
<TD VAlign=top>
See below.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void unique()</tt>
</TD>
<TD VAlign=top>
<tt>list</tt>
</TD>
<TD VAlign=top>
See below.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void merge(list&amp; L)</tt>
</TD>
<TD VAlign=top>
<tt>list</tt>
</TD>
<TD VAlign=top>
See below.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void sort()</tt>
</TD>
<TD VAlign=top>
<tt>list</tt>
</TD>
<TD VAlign=top>
See below.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>
bool operator==(const list&amp;, 
                const list&amp;)
</pre>
</TD>
<TD VAlign=top>
 <A href="ForwardContainer.html">Forward Container</A>
</TD>
<TD VAlign=top>
Tests two lists for equality.  This is a global function, not
   a member function.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>
bool operator&lt;(const list&amp;, 
               const list&amp;)
</pre>
</TD>
<TD VAlign=top>
 <A href="ForwardContainer.html">Forward Container</A>
</TD>
<TD VAlign=top>
Lexicographical comparison.  This is a global function, not
   a member function.
</TD>
</tr>
</table>
<h3>New members</h3>
These members are not defined in the 
<A href="ReversibleContainer.html">Reversible Container</A>, 
<A href="FrontInsertionSequence.html">Front Insertion Sequence</A>, and
<A href="BackInsertionSequence.html">Back Insertion Sequence</A>
requirements, but are specific to <tt>list</tt>.
<Table border>
<TR>
<TH>
Function
</TH>
<TH>
Description
</TH>
</TR>
<TR>
<TD VAlign=top>
<pre>
void splice(iterator position, 
            list&lt;T, Alloc&gt;&amp; x);
</pre>
</TD>
<TD VAlign=top>
<tt>position</tt> must be a valid iterator in <tt>*this</tt>, and <tt>x</tt> must be a list that
   is distinct from <tt>*this</tt>.  (That is, it is required that
   <tt>&amp;x != this</tt>.)  All of the elements of <tt>x</tt> are inserted before
   <tt>position</tt> and removed from <tt>x</tt>.  All iterators remain valid, 
   including iterators that point to elements of <tt>x</tt>. <A href="#3">[3]</A> This function is 
   constant time.  
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre> 
void splice(iterator position, 
            list&lt;T, Alloc&gt;&amp; x,
            iterator i);
</pre>
</TD>
<TD VAlign=top>
<tt>position</tt> must be a valid iterator in <tt>*this</tt>, and <tt>i</tt> must be a
   dereferenceable iterator in <tt>x</tt>.  <tt>Splice</tt> moves the element
   pointed to by <tt>i</tt> from <tt>x</tt> to <tt>*this</tt>, inserting it before
   <tt>position</tt>.  All iterators remain valid, including iterators that point
   to elements of <tt>x</tt>. <A href="#3">[3]</A>  If <tt>position == i</tt> or <tt>position == ++i</tt>,
   this function is a null operation.  This function is constant time. 
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre> 
void splice(iterator position, 
            list&lt;T, Alloc&gt;&amp; x,
            iterator f, iterator l);
</pre>
</TD>
<TD VAlign=top>
<tt>position</tt> must be a valid iterator in <tt>*this</tt>, and <tt>[first, last)</tt>
   must be a valid range in <tt>x</tt>.  <tt>position</tt> may not be an iterator
   in the range <tt>[first, last)</tt>.  <tt>Splice</tt> moves the elements 
   in <tt>[first, last)</tt> from <tt>x</tt> to <tt>*this</tt>, inserting them before
   <tt>position</tt>.  All iterators remain valid, including iterators that
   point to elements of <tt>x</tt>. <A href="#3">[3]</A>  This function is constant time. 
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void remove(const T&amp; val);</tt>
</TD>
<TD VAlign=top>
Removes all elements that compare equal to <tt>val</tt>.  The relative order
   of elements that are not removed is unchanged, and iterators to 
   elements that are not removed remain valid.  This function is 
   linear time: it performs exactly <tt>size()</tt> comparisons for equality.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>
template&lt;class <A href="Predicate.html">Predicate</A>&gt; 
void remove_if(<A href="Predicate.html">Predicate</A> p); 
<A href="#4">[4]</A>
</pre>
</TD>
<TD VAlign=top>
Removes all elements <tt>*i</tt> such that <tt>p(*i)</tt> is true.  The relative
   order of elements that are not removed is unchanged, and iterators to
   elements that are not removed remain valid.  This function is linear
   time: it performs exactly <tt>size()</tt> applications of <tt>p</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void unique();</tt>
</TD>
<TD VAlign=top>
Removes all but the first element in every consecutive group of
   equal elements.  The relative order
   of elements that are not removed is unchanged, and iterators to 
   elements that are not removed remain valid.  This function is 
   linear time: it performs exactly <tt>size() - 1</tt> comparisons for equality.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>
template&lt;class <A href="BinaryPredicate.html">BinaryPredicate</A>&gt;
void unique(<A href="BinaryPredicate.html">BinaryPredicate</A> p); 
<A href="#4">[4]</A>
</pre>
</TD>
<TD VAlign=top>
Removes all but the first element in every consecutive group of
   equivalent elements, where two elements <tt>*i</tt> and <tt>*j</tt> are considered
   equivalent if <tt>p(*i, *j)</tt> is true.  The relative order
   of elements that are not removed is unchanged, and iterators to 
   elements that are not removed remain valid.  This function is 
   linear time: it performs exactly <tt>size() - 1</tt> comparisons for
   equality. 
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void merge(list&lt;T, Alloc&gt;&amp; x);</tt>
</TD>
<TD VAlign=top>
Both <tt>*this</tt> and <tt>x</tt> must be sorted according to <tt>operator&lt;</tt>, and
   they must be distinct.
   (That is, it is required that <tt>&amp;x != this</tt>.)  This function removes
   all of <tt>x</tt>'s elements and inserts them in order into <tt>*this</tt>.  The merge is
   stable; that is, if an element from <tt>*this</tt> is equivalent to one from
   <tt>x</tt>, then the element from <tt>*this</tt> will precede the one from <tt>x</tt>.
   All iterators to elements in <tt>*this</tt> and <tt>x</tt> remain valid.  
   This function is linear time:  it performs at most <tt>size() + x.size()
   - 1</tt> comparisons.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>
template&lt;class <A href="BinaryPredicate.html">BinaryPredicate</A>&gt;
void merge(list&lt;T, Alloc&gt;&amp; x, 
           BinaryPredicate Comp); 
<A href="#4">[4]</A>
</pre>
</TD>
<TD VAlign=top>
<tt>Comp</tt> must be a comparison function that induces a strict weak
   ordering (as defined in the <A href="LessThanComparable.html">LessThan Comparable</A> requirements)
   on objects of type <tt>T</tt>, and both <tt>*this</tt> and <tt>x</tt> must be sorted
   according to that ordering.  The lists <tt>x</tt> and <tt>*this</tt> must be 
   distinct.  (That is, it is required that <tt>&amp;x != this</tt>.)
   This function removes
   all of <tt>x</tt>'s elements and inserts them in order into <tt>*this</tt>.  The merge is
   stable; that is, if an element from <tt>*this</tt> is equivalent to one from
   <tt>x</tt>, then the element from <tt>*this</tt> will precede the one from <tt>x</tt>.
   All iterators to elements in <tt>*this</tt> and <tt>x</tt> remain valid.  
   This function is linear time:  it performs at most <tt>size() + x.size()
   - 1</tt> applications of <tt>Comp</tt>. 
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void reverse();</tt>
</TD>
<TD VAlign=top>
Reverses the order of elements in the list.  All iterators remain
   valid and continue to point to the same elements. <A href="#5">[5]</A> This function
   is linear time.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void sort();</tt>
</TD>
<TD VAlign=top>
Sorts <tt>*this</tt> according to <tt>operator&lt;</tt>.  The sort is stable, that is,
   the relative order of equivalent elements is preserved.  
   All iterators remain 
   valid and continue to point to the same elements. <A href="#6">[6]</A>  The number
   of comparisons is approximately <tt>N log N</tt>, where <tt>N</tt> is the <tt>list</tt>'s
   size.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>
template&lt;class <A href="BinaryPredicate.html">BinaryPredicate</A>&gt;
void sort(BinaryPredicate comp); 
<A href="#4">[4]</A>
</pre>
</TD>
<TD VAlign=top>
<tt>Comp</tt> must be a comparison function that induces a strict weak
   ordering (as defined in the <A href="LessThanComparable.html">LessThan Comparable</A> requirements
   on objects of type <tt>T</tt>.  This function sorts the list
   <tt>*this</tt> according to <tt>Comp</tt>.  The sort is stable, that is,
   the relative order of equivalent elements is preserved.  
   All iterators remain 
   valid and continue to point to the same elements. <A href="#6">[6]</A>  The number
   of comparisons is approximately <tt>N log N</tt>, where <tt>N</tt> is the <tt>list</tt>'s
   size.
</TD>
</tr>
</table>
<h3>Notes</h3>
<P><A name="1">[1]</A>
A comparison with <tt><A href="Vector.html">vector</A></tt> is
instructive.  Suppose that <tt>i</tt> is a valid
<tt><A href="Vector.html">vector</A>&lt;T&gt;::iterator</tt>.  If an element
is inserted or removed in a position that precedes <tt>i</tt>, then
this operation will either result in <tt>i</tt> pointing to a
different element than it did before, or else it will invalidate
<tt>i</tt> entirely.  (A
<tt><A href="Vector.html">vector</A>&lt;T&gt;::iterator</tt> will be
invalidated, for example, if an insertion requires a reallocation.)
However, suppose that <tt>i</tt> and <tt>j</tt> are both iterators
into a <A href="Vector.html">vector</A>, and there exists some integer
<tt>n</tt> such that <tt>i == j + n</tt>.  In that case, even if
elements are inserted into the vector and <tt>i</tt> and <tt>j</tt>
point to different elements, the relation between the two iterators
will still hold.  A <tt>list</tt> is exactly the opposite: iterators
will not be invalidated, and will not be made to point to different
elements, but, for <tt>list</tt> iterators, the predecessor/successor
relationship is not invariant.
<P><A name="2">[2]</A>
This member function relies on <i>member template</i> functions, which
at present (early 1998) are not supported by all compilers.  If your
compiler supports member templates, you can call this function with
any type of <A href="InputIterator.html">input iterator</A>.  If your
compiler does not yet support member templates, though, then the
arguments must either be of type <tt>const value_type*</tt> or of type
<tt>list::const_iterator</tt>.
<P><A name="3">[3]</A>
A similar property holds for all versions of <tt>insert()</tt> and
<tt>erase()</tt>.  <tt>List&lt;T, Alloc&gt;::insert()</tt> never
invalidates any iterators, and  <tt>list&lt;T, Alloc&gt;::erase()</tt>
only invalidates iterators pointing to the elements that are actually
being erased.
<P><A name="4">[4]</A>
This member function relies on <i>member template</i> functions, which
at present (early 1998) are not supported by all compilers.
You can only use this member function if your compiler supports
member templates.
<P><A name="5">[5]</A>
If <tt>L</tt> is a list, note that <tt>L.reverse()</tt> and 
<tt><A href="reverse.html">reverse</A>(L.begin(), L.end())</tt> are both
correct ways of reversing the list.  They differ in that
<tt>L.reverse()</tt> will preserve the value that each iterator into
<tt>L</tt> points to but will not preserve the iterators'
predecessor/successor relationships, while
<tt><A href="reverse.html">reverse</A>(L.begin(), L.end())</tt> will not
preserve the value that each iterator points to but will preserve the
iterators' predecessor/successor relationships.  Note also that the
algorithm <tt><A href="reverse.html">reverse</A>(L.begin(), L.end())</tt> 
will use <tt>T</tt>'s assignment operator, while the 
member function <tt>L.reverse()</tt> will not.
<P><A name="6">[6]</A>
The <tt><A href="sort.html">sort</A></tt> algorithm  works only for 
<A href="RandomAccessIterator.html">random access iterators</A>.  In
principle, however, it would be possible to write a sort algorithm
that also accepted <A href="BidirectionalIterator.html">bidirectional iterators</A>.
Even if there were such a version of
<tt><A href="sort.html">sort</A></tt>, it would still be useful for
<tt>list</tt> to have a <tt>sort</tt> member function.  That is,
<tt>sort</tt> is provided as a member function not only for the sake
of efficiency, but also because of the property that it preserves the
values that list iterators point to.
<h3>See also</h3>
<A href="BidirectionalIterator.html">Bidirectional Iterator</A>,
<A href="ReversibleContainer.html">Reversible Container</A>,
<A href="Sequence.html">Sequence</A>,
<tt><A href="Slist.html">slist</A></tt>
<tt><A href="Vector.html">vector</A></tt>.

<!--start footer--> 
<HR SIZE="6">
<A href="http://www.sgi.com/"><IMG SRC="surf.gif" HEIGHT="54" WIDTH="54" 
        ALT="[Silicon Surf]"></A>
<A HREF="index.html"><IMG SRC="stl_home.gif" 
        HEIGHT="54" WIDTH="54" ALT="[STL Home]"></A>
<BR>
<FONT SIZE="-2">
<A href="http://www.sgi.com/Misc/sgi_info.html" TARGET="_top">Copyright &copy; 
1999 Silicon Graphics, Inc.</A> All Rights Reserved.</FONT>
<FONT SIZE="-3"><a href="http://www.sgi.com/Misc/external.list.html" TARGET="_top">TrademarkInformation</A>
</FONT>
<P>
</BODY>
</HTML> 
